package com.abel.day0305;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author xiachao
 * @date 2019/3/5
 */
public class Solution {

    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> ret = new ArrayList<Integer>();
        if(input.length < k){
            return ret;
        }
        int len = input.length;
        for(int i=0;i<k;i++){
            for(int j=0;j<len-1-i;j++){
                if(input[j]<input[j+1]){
                    int t = input[j];
                    input[j] = input[j+1];
                    input[j+1] = t;
                }
            }
        }
        for(int i=len-1;i>len-k-1;i--){
            ret.add(input[i]);
        }
        return ret;
    }

    public int FindGreatestSumOfSubArray(int[] array) {
        int len = array.length;
        int max = array[0];
        for(int i=0;i<len;i++){
            int cur = 0;
            for(int j=i;j<len;j++){
                cur+=array[j];
                if(cur > max){
                    max =cur;
                }
            }
        }
        return max;
    }

    public int NumberOf1Between1AndN_Solution(int n) {
        int count = 0;
        for(int i=1;i<=n;i++){
            int t = i;
            while(t>0){
                int a = t % 10;
                if(a == 1){
                    count++;
                }
                t /= 10;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        //int [] array = {6,-3,-2,7,-15,1,2,2};
        //System.out.println(new Solution().GetLeastNumbers_Solution(input, 4));
        //System.out.println(new Solution().FindGreatestSumOfSubArray(array));
        System.out.println(new Solution().NumberOf1Between1AndN_Solution(13));
    }

}
